#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/11/19
# @Author   :Changshu
# @File     :Exercise_455.py
# 455. 分发饼干

'''暴力寻找,是可行的，
	时间复杂度：O(m*n)
	空间复杂度：O(n)

def findContentChildren(g: list, s: list) -> int:
	count=0
	s_got=[0]*len(s)
	for i in range(len(g)):
		gap = 2 ** 31 - 1
		selected = -1
		for j in range(len(s)):
			if 0<=s[j]-g[i]<gap and s_got[j]==0:
				gap=s[j]-g[i]
				selected=j
		if selected!=-1:
			count+=1
			s_got[selected]=1
	return count
'''

'''最终还是要排序的，排完序就可以使用贪心策略了'''
def findContentChildren(g: list, s: list) -> int:
	g.sort()
	s.sort()
	child=0
	cookie=0
	while(child<len(g) and cookie<len(s)):
		if g[child]<=s[cookie]:
			child+=1
		cookie+=1
	return child



if __name__ == '__main__':
	g=[1,2,3,4,5,6]
	# g=[]
	# s=[3,4,5]
	s=[]
	print(findContentChildren(g,s))